#ifndef _COMMON_SORT_H
#define _COMMON_SORT_H

#include <iostream>
#include <vector>

class BubbleSort {
public:
	static void sort(std::vector<int>& vec);
};

class RecursiveBubbleSort {
public:
	static void sort(std::vector<int>& vec, size_t sz);
};

class InsertionSort {
public:
	static void sort(std::vector<int>& vec);
};

class RecursiveInsertionSort {
public:
	static void sort(std::vector<int>& vec, size_t sz);
};

class SelectionSort {
public:
	static void sort(std::vector<int>& vec);
};

class ShellSort {
public:
	static void sort(std::vector<int>& vec);
};

// recursive merge sort
class MergeSort {
public:
	static void sort(std::vector<int>& vec);
	static void merge(std::vector<int>& vec, int left, int mid, int right);
	static void mergeSort(std::vector<int>& vec, int start, int end);
};

// iterative merge sort
class IterativeMergeSort {
public:
	static void sort(std::vector<int>& vec);
	static void merge(std::vector<int>& vec, int left, int mid, int right);
};

class HeapSort {
public:
	static void sort(std::vector<int>& vec);
	// 从rootIndex开始往下堆化
	static void heapify(std::vector<int>& vec, int sz, int rootIndex);
};

// recursive quick sort
class QuickSort {
public:
	static void sort(std::vector<int>& vec);
	static int partition(std::vector<int>& vec, int start, int end);
	static void quickSort(std::vector<int>& vec, int start, int end);
};

// iterative quick sort
class IterativeQuickSort {
public:
	static void sort(std::vector<int>& vec);
	static int partition(std::vector<int>& vec, int start, int end);
};

// counting sort
class CountingSort {
public:
	static void sort(std::vector<int>& vec);
};

// radix sort
class RadixSort {
public:
	static void sort(std::vector<int>& vec);
	static void countSort(std::vector<int>& vec, int exp);
};

// bucket sort
class BucketSort {
public:
	static void sort(std::vector<int>& vec);
};

// comb sort
class CombSort {
public:
	static void sort(std::vector<int>& vec);
};

#endif

